1198F - GCD Groups 2 - CodeForces Solution

// Problem: F. GCD Groups 2
// Contest: Codeforces - Codeforces Round 576 (Div. 1)
// URL: https://codeforces.com/contest/1198/problem/F
// Memory Limit: 256 MB
// Time Limit: 500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long int
//#define  m 1000000007

using namespace std;

random_device rd;
mt19937 rnd(rd());

//Findout buggs:

#define BUG

#ifdef BUG
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define bug(...)
#endif

//...................
const ll N = 2e5 + 5;
vector<ll> ans;
vector<pair<ll, ll>> a;
ll n;

ll solve(ll i, ll lg, ll rg){
	if(lg == 1 && rg == 1) return 1;
	ll x = __gcd(lg, a[i].first);
	ll y = __gcd(rg, a[i].first);
	if(i == n) return 0;
	if(x == lg && y == rg){
		return solve(i + 1, x, y);
	}
	else {
		if(x != lg){
			ans[a[i].second] = 1;
			if(solve(i + 1, x, rg)) return 1;
		}
		if(y != rg){
			ans[a[i].second] = 0;
			if(solve(i + 1, lg, y)) return 1;
		}
		return 0;
	}
	return 0;
}

int32_t main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
	
	cin >> n;
	a = vector<pair<ll, ll>> (n);
	ans = vector<ll> (n);
	for(ll i = 0; i< n; i++) cin >> a[i].first, a[i].second = i;
	
	shuffle(a.begin(),a.end(),rnd);
	
	ll ok = solve(0, 0, 0);
	if(ok){
		cout << "YES" << '\n';
		for(ll i = 0; i < n; i++){
			cout << ans[i] + 1 << ' ';
		}
	}
	else cout << "NO" << '\n';
	
	
	return 0;
}